DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.17

Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function

Authors: Yang Du and Ilya Volkovich

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

In this work we devise the first efficient deterministic algorithm for approximating ω(N) - the number of prime factors of an integer N ∈ ℕ, given in addition oracle access to Euler’s Totient function Φ(⋅). We also show that the algorithm can be extended to handle a more general class of additive functions that "depend solely on the exponents in the prime factorization of an integer". In particular, our result gives the first algorithm that approximates ω(N) without necessarily factoring N. Indeed, all the previously known algorithms for computing or even approximating ω(N) entail factorization of N, and therefore are either randomized [M. O. Rabin, 1980; D. L. Long, 1981] or require the Generalized Riemann Hypothesis (GRH) [G. L. Miller, 1976]. Our approach combines an application of Coppersmith’s method for finding non-trivial factors of integers whose prime factors satisfy certain "relative size" conditions of [F. Morain et al., 2018], together with a new upper bound on Φ(N) in terms of ω(N) which could be of independent interest.

Cite as

Yang Du and Ilya Volkovich. Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{du_et_al:LIPIcs.FSTTCS.2021.17,
  author =	{Du, Yang and Volkovich, Ilya},
  title =	{{Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-155286},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.17},
  annote =	{Keywords: Euler’s Totient Function, Integer Factorization, Number of Prime Factors, Derandomization}
}

Search Results

Documents authored by Du, Yang

Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function

Abstract

Cite as

Thanks for your feedback!

Could not send message